﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LL
{
    class LL
    {
        public LLNode head = null;
        public LL(params int[] a)
        {
            foreach (var item in a)
            {
                Add(item);
            }
        }

        private void Add(int item)
        {
            if (head == null)
            {
                head = new LLNode { n = item, next = null };
                return;
            }
            LLNode t = head;
            while (t.next != null)
                t = t.next;
            t.next = new LLNode { n = item, next = null };
        }

        public void Display(LLNode head1)
        {
            Console.WriteLine();
            if (head1 == null)
                return;
            LLNode t = head1;
            while (t != null)
            {
                Console.Write(t.n + " ");
                t = t.next;
            }
        }

        public LLNode Reverse(LLNode head1)
        {
            LLNode prev = null;
            LLNode next = null;
            while (head1 != null)
            {
                next = head1.next;
                head1.next = prev;
                prev = head1;
                head1 = next;
            }
            return prev;
        }

        public LLNode GetSecondHalfHead(LLNode start)
        {
            LLNode t = start.next;
            while (t != null || t.next != null)
            {
                if (t.next == null || t.next.next == null)
                    break;
                t = t.next.next;
                start = start.next;
            }
            LLNode t1 = start.next;
            start.next = null;
            return t1;
        }

        public LLNode MergeAlterNate(LLNode a, LLNode b)
        {
            if (a == null && b == null)
                return null;
            if (a != null && b == null)
                return a;
            if (a == null && b != null)
                return b;
            a.next = MergeAlterNate(b, a.next);
            return a;
        }

        public LLNode PartitionEvenOdd(LLNode head2)
        {
            LLNode head1 = head2;
            LLNode evenNode = null;
            LLNode oddNode = null;
            LLNode prev = null;
            while (head1.next != null)
            {
                if (head1.n % 2 == 0)
                {
                    LLNode t2 = head1.next;
                    if (evenNode == null)
                    {
                        evenNode = head1;
                        evenNode.next = null;
                    }
                    else
                    {
                        LLNode t = evenNode;
                        while (t.next != null)
                            t = t.next;
                        t.next = head1;
                        head1.next = null;
                    }
                    if (prev == null)
                    {
                        //temp = t2;
                        prev = t2;
                    }
                    else
                        prev.next = t2;
                    head1 = t2;
                }
                else
                {
                    if (oddNode == null)
                        oddNode = head1;
                    prev = head1;
                    head1 = head1.next;
                }
            }
            if (head2.n % 2 == 0)
            {
                LLNode temp = evenNode;
                while (temp.next != null)
                    temp = temp.next;
                temp.next = oddNode;
                head = evenNode;
            }
            else
            {
                LLNode temp = oddNode;
                while (temp.next != null)
                    temp = temp.next;
                temp.next = evenNode;
                head = oddNode;
            }
            return head;
        }
    }
        

    public class LLNode
    {
        public int n;
        public LLNode next;
    }
}
